package com.bluebridgecup.DP;

import java.util.Scanner;

public class 采药 {
    static Scanner in = new Scanner(System.in);

    public static void main(String[] args) {
        // 读取背包容量V
        int V = in.nextInt();
        // 读取物品的数量N
        int N = in.nextInt();

        // 定义数组v用于存储每个物品的体积，数组长度为N+1，下标从1开始使用
        int[] v = new int[N + 1];
        // 定义数组w用于存储每个物品的价值，数组长度为N+1，下标从1开始使用
        int[] w = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            // 读取第i个物品的体积
            v[i] = in.nextInt();
            // 读取第i个物品的价值，并存储
            w[i] = in.nextInt();
        }
        // 定义二维数组dp，dp[i][j]表示前i个物品在背包容量为j时的最大价值
        int[][] dp = new int[N + 1][V + 1];
        // 初始化边界条件，当没有物品时，背包容量为0时，最大价值为0
        dp[0][0] = 0;

        // 外层循环遍历每个物品，从第1个物品到第N个物品
        for(int i=1;i<=N;i++){
            // 内层循环遍历背包的所有可能容量，从0到v
            for(int j=1;j<=V;j++){
                // 判断当前背包容量j是否足够装下第i个物品
                if(j>=v[i]){
                    // 如果足够装下，选择装或者不装两种情况的最大值
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);

                }else{
                    // 如果装不下，只能选择不装
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        // 输出最终结果，即前N个物品在背包容量为V时的最大价值
        System.out.println(dp[N][V]);
    }
}
